Closures

In Lisp, functions are first-class data objects: they can be created on the fly, passed as arguments, and returned as values. Function objects are created in Common Lisp by passing a lambda expression to the special function FUNCTION.1 The result of FUNCTION is a new function object whose parent contour is the current contour, and whose parameter list and body are taken from the lambda expression. These function objects are also known as lexical closures. We will denote these function objects as #<Lexical-closure A>, #<Lexical-closure B>, and so on.

One of the most common uses for lexical closures is as arguments to applicative operators such as MAPCAR. In the example below, ZERO-CENTER takes a list of numbers as input and adjusts them so that their sum is zero without changing any of the distances between pairs of individual elements. It does this by subtracting the average of the list (computed by AVERAGE) from each element. ZERO-CENTER creates a function object (a lexical closure) to do this subtraction, and passes it to MAPCAR so that it can be applied to each element in succession.


\begin{code} (defun average (seq) (/ (reduce \char93 '+ seq) (length seq))) \st... ...(- x avg)) data))) \strut (zero-center '(3 11 13)) {\et -->} (-6 2 4) \end{code}

Figure: Evaltrace diagram illustrating functional arguments.
\begin{figure}{\noindent\rule{\textwidth}{.01in}} \par \begin{evaltrace} +--> ;(... ... 2 4) \end{evaltrace}\par\par {\noindent\rule{\textwidth}{.01in}} \end{figure}

The function object passed to MAPCAR contains a reference to the variable AVG in its body. Therefore, it is important that the closure's parent contour be the contour where the closure was created, not the global contour, in order for the closure to be able to access ZERO-CENTER's local variable AVG. This relationship is depicted in Figure [*].

Notice that MAPCAR's contour is interposed between the contour created by the LET body and the contours for each invocation of #<Lexical-closure A>. MAPCAR's parent contour is the global contour. But this doesn't matter, because the closure doesn't find its parent by looking for the most recently created contour (i.e., just below the top of the call stack). The parent is determined at the time the closure is defined, and it is remembered explicitly as part of the closure object itself. In the evaltrace diagram, each time the closure is invoked by MAPCAR, its parent contour is shown by a leftward-pointing arrow that appears to ``jump over'' the MAPCAR contour to point to the LET body where the closure was defined. What's really happening is that the closure is ``remembering'' that the LET body's contour is its parent; it ignores the contour created by the invocation of MAPCAR.

This behavior is consistent with our textual-inclusion explanation. The text for the lambda expression that gave rise to the closure appears inside the body of the LET, so the LET forms part of the closure's environment. There is no reason for the closure to be able to access any of the local variables of MAPCAR, since it does not appear within the body of the definition of MAPCAR.

Functions created solely to be passed as arguments are known as funargs in Lisp. They have the property that their parent contour is always somewhere below them on the call stack, although as in the preceding example it will not be immediately below them. Early Lisp dialects (as well as many block-structured languages like Pascal and Ada) allowed function objects to be used only as funargs: a function object could be passed to other functions, but it could not be returned as a value by the function that created it, because then its parent contour would no longer be on the call stack. In Scheme and Common Lisp this restriction has been eliminated; it is possible for contours to remain in existence even after the function call that created them has returned. This is accomplished by locating the contour in heap storage rather than on the stack, when necessary. (Actually, real implementations use many different strategies for representing contours in memory. As a conceptual device, however, it is useful to think in terms of the representation of contours in the heap and stack.) This means that we need a special way to draw contours for functions that are returned as values. Consider the function SHIFTER below, which returns a closure that references SHIFTER's local variable KONST:


\begin{code} (defun shifter (konst) \char93 '(lambda (x) (- x konst))) \end{code}

Below we have rewritten the function ZERO-CENTER in order to demonstrate the use of the closures returned by SHIFTER. ZERO-CENTER calls SHIFTER to create a closure that will subtract the average value from its input. It then uses MAPCAR to apply this closure to ZERO-CENTER's input values, DATA.


\begin{code} (defun zero-center (data) (mapcar (shifter (average data)) data)) \end{code}

Figure: Evaltrace diagram illustrating closures.
\begin{figure}{\noindent\rule{\textwidth}{.01in}} \par \begin{evaltrace} +--> ;... ... 2 4) \end{evaltrace}\par\par {\noindent\rule{\textwidth}{.01in}} \end{figure}

When SHIFTER returns a lexical closure, its parent contour, SHIFTER's contour, is preserved on the heap. This is shown in the evaltrace diagram in Figure [*] as a box on the left in which the local variables of the contour reside. The local variable KONST resides in this box. When the closure is invoked within the body of MAPCAR, its parent contour is this preserved contour. Within the body of the closure, the symbol X evaluates to its local value because X is a local variable in the closure's contour; the symbol KONST evaluates to 9 because there is a variable by that name visible in the parent contour.

Just like other data objects that are allocated in the heap, the contour for the lexical closure can be garbage collected when there are no longer any pointers to it.